import java.util.*;
//大根堆
class IntBig implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}
public class TestHeap{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //Top-k 问题
        int[] arr1 = {71,84,95,12,86,62,47,1,3,98,51};
        System.out.println("请输入要查询数组的前几位最小值:");
        int k = in.nextInt();
        //法1(1). 模拟小根堆,排序取前k个元素
        heapSort(arr1);
        for(int i = 0;i < k;i++){
            System.out.print(arr1[i] + " ");
        }
        System.out.println();
        //法1(2). 直接创建小根堆,排序取前k个元素
        arr1 = new int[]{71,84,95,12,86,62,47,1,3,98,51};
        arr1 = HeapSort(arr1,k);
        System.out.println(Arrays.toString(arr1));
        System.out.println();
        //法2(2). 重写compare,创建大小为k的大根堆,
        // 不断将小于堆顶的元素与堆顶交换,最后剩余的
        // 大根堆就是我们要找的前k个最小元素
        arr1 = new int[]{71,84,95,12,86,62,47,1,3,98,51};
        arr1 = Heapsort(arr1,k);
        System.out.println(Arrays.toString(arr1));
    }
    public static int[] Heapsort(int[] array,int k){
        //创建大根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>(new IntBig());
        int[] arr = new int[k];

        for(int i = 0;i < k;i++){
            queue.offer(array[i]);
        }
        for(int i = k;i < array.length;i++){
            if(array[i] < queue.peek()){
                queue.poll();
                queue.offer(array[i]);
            }
        }
        for(int i = k - 1;i >= 0;i--){
            arr[i] = queue.poll();
        }
        return arr;
    }
    public static int[] HeapSort(int[] array,int k){
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i = 0;i < array.length;i++){
            queue.offer(array[i]);
        }
        int[] arr = new int[k];
        for(int i = 0;i < k;i++){
            arr[i] = queue.poll();
        }
        return arr;
    }
    public static void heapSort(int[] array){
        createHeap(array);
        int len = array.length;
        for(int i = len - 1;i > 0;i--){
            swap(array,0,i);
            siftDown(array,0,i);
        }
    }
    public static void createHeap(int[] array){
        int len = array.length;
        int parent = (len - 1 - 1) / 2;
        for(int i = parent;i >= 0;i--){
            siftDown(array,i,len);
        }
    }
    public static void siftDown(int[] array,int parent,int end){
        int child = parent * 2 + 1;
        while(child < end){
            if(child + 1 < end && array[child] < array[child + 1]){
                child++;
            }
            if(array[child] > array[parent]){
                swap(array,child,parent);
                parent = child;
                child = parent * 2 + 1;
            }else {
                break;
            }
        }
    }
    public static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}
// 80 65 34 25 49 27 19 18 15 28 37
// 80 65 34 27 49 19 28 15 25 18 37
